package java02;

import java.util.Arrays;

public class InserTionSort {
	public static void main(String[] args) {
		int[] a={5,3,7,2,9,8,1,4};
		insertionSort(a);
	}

//	public static void inserTionSort(int[] a) {
//		for(int i=1;i<a.length;i++){
//			for(int j=i-1;j>=0;j--){
//				if(a[j+1]<a[j]){
//					swap(a,j+1,j);
//				}
//			}
//			System.out.println(Arrays.toString(a));
//		}
//	}
//	
//	private static void swap(int[] a, int i, int j) {
//		int t=a[i];
//		a[i]=a[j];
//		a[j]=t;
//	}
	
	public static void insertionSort(int[] a) {  
        for (int i = 1; i < a.length; i++) {  
            int key = a[i];  
            int j = i - 1;  
            while (j >= 0 && a[j] > key) {  
                a[j + 1] = a[j];  
                j = j - 1;  
            }  
            a[j + 1] = key;  
        }  
    } 
}
